import java.util.BitSet;


public class Bits {

	private boolean[] data;

	public Bits (int size) {
		data = new boolean[size];
	}

	public Bits (BitSet b, int size) {
		this(size);
		for (int k=0; k<size; k++) {
			data[k] = b.get(k);
		}
	}

	public int size () {
		return data.length;
	}

	public boolean get (int index) {
		return data[index];
	}

	public void set (int index) {
		data[index] = true;
	}

	public void set (int index, boolean val) {
		data[index] = val;
	}

	public int cardinality () {
		int count = 0;
		for (int k=0; k<data.length; k++) {
			if (data[k])
				count++;
		}
		return count;
	}

	public int numZeros(){
		return size() - cardinality();
	}

	public void set (int begin, int end) {
		for (int k=begin; k<=end; k++)
			data[k] = true;
	}

	public void andNot (Bits b) {
		if (b.size() != size())
			throw new IllegalArgumentException ("size mismatch");
		for (int k=0; k<data.length; k++) {
			data[k] = data[k] && (!b.data[k]);
		}
	}

	public void or (Bits b) {
		if (b.size() != size())
			throw new IllegalArgumentException ("size mismatch");
		for (int k=0; k<data.length; k++) {
			data[k] = data[k] || b.data[k];
		}
	}

	public void and (Bits b) {
		if (b.size() != size())
			throw new IllegalArgumentException ("size mismatch");
		for (int k=0; k<data.length; k++) {
			data[k] = data[k] && b.data[k];
		}
	}

	public Bits clone () {
		Bits tmp = new Bits(size());
		for (int k=0; k<size(); k++) {
			tmp.data[k] = data[k];
		}
		return tmp;
	}

	public int nextSetBit (int begin) {
		if(cardinality()>0){
			int ref = 0;
			for (int k=0; k<size(); k++){
				ref = (k + begin)%size();
				if (data[ref])
					return ref;
			}
		}
		return -1;
	}

	public int nextClearBit (int begin) {
		if(numZeros()>0){
			int ref = 0;
			for (int k=0; k<size(); k++){
				ref = (k + begin)%size();
				if (!data[ref])
					return ref;
			}
		}
		return -1;
	}



	public int randomClearBit(){
		int start = (int)(Math.random()*(size()-1));
		return nextClearBit(start);
	}

	public int randomSetBit(){
		int start = (int)(Math.random()*(size()-1));
		return nextSetBit(start);
	}


	public void clear () {
		for (int k=0; k<size(); k++)
			data[k] = false;
	}

	public BitSet bitSet () {
		BitSet tmp = new BitSet(size());
		for (int k=0; k<size(); k++) {
			tmp.set(k, data[k]);
		}
		return tmp;
	}

	public String toString () {
		StringBuilder str = new StringBuilder ();
		for (int k=0; k<size(); k++) {
			if (data[k])
				str.append('x');
			else
				str.append('_');
		}
		return new String (str);
	}
}
